# Question 1
# ============

# CCC = 111 (base 4) = 1*4^2 + 1*4^1 + 1*4^0 = 21 (base 10)
#     => 21 mod 13 = 8

# ACG = 012 (base 4) = 0*4^2 + 1*4^1 + 2*4^0 = 6 (base 10)
#     => 6 mod 13 = 6

# GAG = 202 (base 4) = 2*4^2 + 0*4^1 + 2*4^0 = 34 (base 10)
#     => 34 mod 13 = 8

# Question 2 et 3
# ===============

def f_CodeBase4(sequence):
    dic = {'A':0, 'C':1, 'G':2, 'T':3}
    val_base4 = []
    for lettre in sequence:
        val_base4.append(dic[lettre])
    return val_base4

def f_HashCode(val_b4):
    val = 0
    for i in range(3):
        val = val + val_b4[i]*pow(4,2-i)
    return val%13

print(f_HashCode([2,0,2]))
print(f_HashCode([1,1,1]))
print(f_HashCode([0,1,2]))


# Question 4
# ==========

def f_Eval(P,b):
    val = 0
    for i in range(len(P)):
        val = val + P[i]*pow(b,len(P)-1-i)
    return val

print(f_Eval([2,0,2],4))
print(f_Eval([0,1,2],4))


# Question 5 : Il faut (k-1) multiplications et on doit le faire pour tous les
#              k de 1 à n : 0 + 1 + 2 + ... + (n-1) = (n-1)*n/2
#              Pour chaque k de 0 à n, on a en plus ak*bk : 1 multiplication
#              et il faut ajouter au résultat de la somme courante : n+1 additions
#              Soit : (n-1)*n/2 + (n+1) (multiplications) + (n+1) (additions)
#              soit O(n²) + O(n) = O(n²)


# Question 6 : On itère de 0 à (n-1) et pour chaque itération on fait
#              1 multiplication + 1 addition
#              => 2n opérations => O(n)

# Question 7

def f_Hornerit(P,b):
    r = P[0]
    for i in range(len(P)-1):
        r = r*b + P[i+1]
    return r

def f_Hornerrec(P,b):
    if len(P) == 1:
        return P[0]
    else:
        s=P[len(P)-1]
        s1 = P[:-1]
        return f_Hornerrec(s1,b)*b+s